package com.sheng.leetcode.year2025.month10.day15;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author by ls
 * @date 2025/10/14
 * <p>
 * 3350. 检测相邻递增子数组 II<p>
 * <p>
 * 给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增 子数组。<p>
 * 具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：<p>
 * 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。<p>
 * 这两个子数组必须是 相邻的，即 b = a + k。<p>
 * 返回 k 的 最大可能 值。<p>
 * 子数组 是数组中的一个连续 非空 的元素序列。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [2,5,7,8,9,2,3,4,3,1]<p>
 * 输出：3<p>
 * 解释：<p>
 * 从下标 2 开始的子数组是 [7, 8, 9]，它是严格递增的。<p>
 * 从下标 5 开始的子数组是 [2, 3, 4]，它也是严格递增的。<p>
 * 这两个子数组是相邻的，因此 3 是满足题目条件的 最大 k 值。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [1,2,3,4,4,4,4,5,6,7]<p>
 * 输出：2<p>
 * 解释：<p>
 * 从下标 0 开始的子数组是 [1, 2]，它是严格递增的。<p>
 * 从下标 2 开始的子数组是 [3, 4]，它也是严格递增的。<p>
 * 这两个子数组是相邻的，因此 2 是满足题目条件的 最大 k 值。<p>
 * <p>
 * 提示：<p>
 * 2 <= nums.length <= 2 * 10^5<p>
 * -10^9 <= nums[i] <= 10^9<p>
 */
public class LeetCode3350 {

    @Test
    public void test() {
//        List<Integer> nums = new ArrayList<>(Arrays.asList(2, 5, 7, 8, 9, 2, 3, 4, 3, 1));
        List<Integer> nums = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 4, 4, 4, 5, 6, 7));
        System.out.println(new Solution().maxIncreasingSubarrays(nums));
    }
}

class Solution {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        // 设当前严格递增段的长度为 cnt，前一个严格递增段的长度为 preCnt
        int ans = 0;
        int preCnt = 0;
        int cnt = 0;
        /**
         * 以输入 nums = [1,2,3,4,4,4,4,5,6,7] 为例：
         *
         * 递增段划分：
         * 第一个递增段： [1,2,3,4] ，长度为 4 。
         * 第二个递增段： [5,6,7] ，长度为 3 。
         * 计算 k ：
         * 情况 1： cnt / 2 = 4 / 2 = 2 。
         * 情况 2： min(preCnt, cnt) = min(4, 3) = 3 。
         * 最终 ans = max(2, 3) = 2 （因为 [1,2] 和 [3,4] 是相邻且严格递增的子数组）。
         */
        for (int i = 0; i < nums.size(); i++) {
            cnt++;
            // i 是严格递增段的末尾
            if (i == nums.size() - 1 || nums.get(i) >= nums.get(i + 1)) {
                // 两个子数组属于同一个严格递增段，那么 k 最大是 cnt / 2
                // 两个子数组分别属于一对相邻的严格递增段，那么 k 最大是 min(preCnt, cnt)
                ans = Math.max(ans, Math.max(cnt / 2, Math.min(preCnt, cnt)));
                preCnt = cnt;
                cnt = 0;
            }
        }
        return ans;
    }
}

class SolutionTimeOut {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int n = nums.size();
        if (n < 2) {
            // 边界条件
            return 0;
        }

        int left = 1, right = n / 2;
        int maxK = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (hasIncreasingSubarrays(nums, mid)) {
                // 更新最大 k
                maxK = mid;
                // 尝试更大的 k
                left = mid + 1;
            } else {
                // 尝试更小的 k
                right = mid - 1;
            }
        }
        return maxK;
    }

    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        // 集合内是否存在两个长度为 k 的严格递增子数组，并且这两个子数组必须得是相邻的
        int n = nums.size();
        for (int i = 0; i <= n - 2 * k; i++) {
            boolean isValid = true;
            // 检查第一个子数组 [i, i + k - 1]
            for (int j = i + 1; j < i + k; j++) {
                if (nums.get(j) <= nums.get(j - 1)) {
                    isValid = false;
                    break;
                }
            }
            if (!isValid) {
                // 第一个子数组不满足条件，跳过
                continue;
            }

            // 检查第二个子数组 [i + k, i + 2k - 1]
            for (int j = i + k + 1; j < i + 2 * k; j++) {
                if (nums.get(j) <= nums.get(j - 1)) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return true;
            }
        }
        return false;
    }
}
